МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ Національній університет "Львівська політехніка"
Дослідження роботи методів лінійного програмування МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи №2 з курсу "Методи синтезу та оптимізації" для студентів базового напряму 6.08.04 "Комп'ютерні науки" ЗАТВЕРДЖЕНО на засіданні кафедри САПР Протокол № 1 від 28.08 2008 р. ЛЬВІВ 2008  Дослідження роботи методів лінійного програмування. Методичні вказівки до лабораторної роботи №2 з курсу " Методи синтезу та оптимізації " для студентів базового напряму 6.08.04 "Комп'ютерні науки" /Укл. Андрійчук М. І., Теслюк В.М. - Львів: НУ"ЛП", 2008 р. Укладачі: Андрійчук Михайло Іванович, к. ф.-м. н., доц., Теслюк Василь Миколайович, к.т.н., доц. Відповідальний за випуск: Ткаченко С.П., к.т.н., доц. Рецензенти: Каркульовський В. І., к.т.н., доц., Стех Ю.В, к.т.н., доц. 1. МЕТА РОБОТИ Вивчити основні алгоритми розв’язку задач лінійної оптимізації. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Задачі оптимізації, в яких цільова функція є лінійною функцією незалежних змінних (тобто має вигляд z = c1 x1+ c2 x2+...+ cn xn, де c1, c2,..., cn - константи, x1, x2,..., xn - змінні, n-довільне натуральне число) і умови, які визначають допустимі значення цих змінних мають вигляд лінійних рівнянь і нерівностей, відносять до задач лінійного програмування. Лінійне програмування було розвинене в зв'язку із задачами економіки, з пошуком способів оптимального рішення і з використанням обмежених ресурсів. Розвиток і ускладнення економічних процесів, обчислювальної техніки стимулює широке використання математичних методів в управлінні, сприяє зростанню ролі лінійного програмування як одного з актуальних розділів прикладної математики. Так за оцінками американських експертів біля 75% від загального числа практичних оптимізаційних задач, відносяться до задач ЛП. Біля чверті машинного часу, затраченого в останні роки на проведення наукових досліджень, було відведено рішенню задач ЛП та їх чисельних модифікацій. 2.1. Стандартна форма представлення лінійних задач оптимізації Перед застосуванням симплекс-методу необхідною умовою є запис оптимізаційних задач в стандартній (канонічній) формі. Канонічна форма запису оптимізацій них задач передбачає, що: усі змінні мають бути не від’ємними; нерівності слід перетворити в рівності; праві частини рівнянь мають бути не від’ємними. Стандартна або канонічна постановка задачі лінійного програмування наступна: знайти такі значення змінних x1, x2,..., xn, які задовольняють наступну систему рівнянь:
, (1) і дають найменше значення цільової функції : z = c1*x1+ c2*x2+. .. + cn*xn. 2.2. Графічне рішення задачі ЛП Розглянемо метод графічного рішення ЗЛП на прикладі задачі технічного контролю. Задача технічного контролю. У відділі технічного контролю (ВТК) деякої фірми працюють контролери першого та другого розрядів. Норма вироблення ВТК за 8 - годинний робочий день складає не менше ніж 1800 виробів. Контролер першого розряду перевіряє 25 виробів в годину, причому, не помиляється у 98% випадків. Контролер розряду 2 перевіряє 15 виробів в годину; його точність становить 95%. Заробітна плата контролера першого розряду рівна 4 грн. в годину, а контролер другого розряду отримує 3 грн. в годину. При кожній помилці контролера фірма несе збиток в розмірі 2 грн. Фірма може використати 8 контролерів розряду і 10 контролерів другого розряду. Керіництво фірми хоче визначити оптимальний склад ВТК, при якому загальні витрати на контроль будуть мінімальні. 2.2.1. Розробка моделі. Нехай x1 і x2 означають кількість контролерів першого та другого розрядів, відповідно. Число контролерів кожного розряду, які може використати підприємство обмежене, тобто мають бути включені наступні обмеження: x1
8 (разряд 1), x2
10 (разряд 2). Щодня необхідно перевіряти не менше 1800 виробів. Тому, слід записати наступну нерівність: 8*25*x1+8*15*x2=200*x1+1200*x2
1800, або 5*x1+3*x2
45. При побудові цільової функці...